Definition

Define language L′L' as NP-hard if L≤pL′L \leq_p L' for every L∈L \in NP. (polynomial-time reduction from LL to L′L')

(see NP, also note that ≤p\leq_p means polynomial-time reduction)


References

  1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 42.